import java.util.ArrayList;


public class Knapsack {
	class Item{
		int value;
		int weight;
	}
	int number;
	int size;
	ArrayList<Item> data;
	int [][]A;
	
	public void InitData(){
		DataReader reader = new DataReader();
		reader.SetFilename("C:\\workspace\\testdata\\knapsack1.txt");
		
		String str;
		str = reader.GetNextLine();
		String[] parser = str.split(" ");
		size = Integer.parseInt(parser[0]);
		number = Integer.parseInt(parser[1]);
		data = new ArrayList<Item>(number);
		
		while((str = reader.GetNextLine()) != null)
		{
			parser = str.split(" ");
			Item item = new Item();
			item.value = Integer.parseInt(parser[0]);
			item.weight = Integer.parseInt(parser[1]);
			data.add(item);
		}
	}
	
	public void PrintData(){
		System.out.println("knapsack size is " + size + " item number is " + number);
		
		for(int i = 0; i < data.size(); i++){
			Item item = data.get(i);
			System.out.println(item.value + "\t" + item.weight);
		}
	}
	
	int Max(int a, int b){
		if(a > b)
			return a;
		else
			return b;
	}
	
	public void RunKnapsack(){
		//A[i, w] = max{A[i - 1, w], A[i - 1, w - wi] + Vi}
		
		A = new int[number + 1][size + 1];
		for(int j = 0; j < size + 1; j++){
			A[0][j] = 0;
		}
		
		for(int i = 1; i < number + 1; i++){
			Item item = data.get(i - 1);
			for(int w = 0; w < size + 1; w++){
				if(w - item.weight >= 0){
					A[i][w] = Max(A[i-1][w], A[i-1][w-item.weight] + item.value);
				}
				else{
					A[i][w] = A[i - 1][w];
				}
			}
		}
		
		System.out.println("Optimal value is " + A[number][size]);
	}
}
